//Spanning tree for path
ArrayList<Edge> minEdges = new ArrayList<Edge>();
ArrayList<Integer> triInMinTree = new ArrayList<Integer>();
class SpanningTree{
  ArrayList<Edge> edges;
  ArrayList<Integer> treeVerts = new ArrayList<Integer>();
  SpanningTree(ArrayList<Edge> edges){
    this.edges = edges;
  }
  SpanningTree(){
    this(new ArrayList<Edge>());
  }
  void addEdge(Edge a){
    if(!contains2(a,edges)){
      edges.add(a);
      if(!treeVerts.contains(a.start)){
        treeVerts.add(a.start);
      }
      if(!treeVerts.contains(a.end)){
        treeVerts.add(a.end);
      }
    }
  }
  void addEdge(int start, int end, int count){
    addEdge(new Edge(start,end,count));
  }
  void sortEdges(){
    Collections.sort(edges,new EdgeCompare());
  }
  
  ArrayList<Edge> minimumSpanningTree(){
    sortEdges();
    boolean edgebool = true;
    ArrayList<Edge> minTree = new ArrayList<Edge>();
    ArrayList<Edge> paths = new ArrayList<Edge>();
    ArrayList<Integer> used = new ArrayList<Integer>();
    minTree.add(edges.get(0));
//    used.add(edges.get(0).start);
//    used.add(edges.get(0).end);
    paths.add(edges.get(0));
//    for(Integer v : treeVerts){
//      println("VV " +  v);
//      paths.add(new Edge(v,v,0));
//    }
    for(int j = 1; j<edges.size(); j++){
      edgebool = true;
      int minSize = minTree.size();
//      for(int i = 0; i<minSize; i++){
//        if(!((edges.get(j).start != minTree.get(i).start && edges.get(j).start != minTree.get(i).end) && (edges.get(j).end != minTree.get(i).start && edges.get(j).end != minTree.get(i).end ) )){
//          println(edges.get(j).start);
//          println(edges.get(j).end);
//          println(minTree.get(i).start);
//          println(minTree.get(i).end);
//          println(edges.get(j).toString());
//          println(minTree.get(i).toString());
//          println("------------------");
//          minTree.add(edges.get(j));
//            edgebool=false;
//        }

//      }
//      if(edgebool){
//      if(!used.contains(edges.get(j).start) || !used.contains(edges.get(j).end)){
//        minTree.add(edges.get(j));
//        if(!used.contains(edges.get(j).start)){
//          used.add(edges.get(j).start);
//        }
//        if(!used.contains(edges.get(j).end)){
//          used.add(edges.get(j).end);
//        }
//      }
//      for(Integer i : used){
//        println(i);
//      }
//      println("--------------");
      int pathsize = paths.size();
      for(int i = 0; i<pathsize; i++){
        for(int k = 0; k<pathsize; k++){
          Edge e = new Edge(paths.get(i).end,paths.get(k).end,paths.get(i).count+paths.get(k).count);
          if((paths.get(i).start==paths.get(k).start && paths.get(i).end != paths.get(k).end) && !contains2(e,paths) ){
            paths.add(e);
          }
          e = new Edge(paths.get(i).start,paths.get(k).start,paths.get(i).count+paths.get(k).count);
          if((paths.get(i).start!=paths.get(k).start && paths.get(i).end == paths.get(k).end) && !contains2(e,paths) ){
            paths.add(e);
          }
          e = new Edge(paths.get(i).end,paths.get(k).start,paths.get(i).count+paths.get(k).count);
          if((paths.get(i).start == paths.get(k).end && paths.get(i).end != paths.get(k).start) && !contains2(e,paths) ){
            paths.add(e);
          }
          e = new Edge(paths.get(i).start,paths.get(k).end,paths.get(i).count+paths.get(k).count);
          if((paths.get(i).start != paths.get(k).end && paths.get(i).end == paths.get(k).start) && !contains2(e,paths) ){
            paths.add(e);
          }
        }
      }
      Edge curr = edges.get(j);
      if(!contains2(curr,paths)){
        minTree.add(curr);
        paths.add(curr);
      }
      
    }
    return minTree;
  }
  
  boolean contains(Edge e, ArrayList<Edge> lis){
    for(Edge i : lis){
      if(e.start == i.start && e.end==i.end){
        return true;
      }
    }
    return false;
  }
  
  boolean contains2(Edge e, ArrayList<Edge> lis){
    for(Edge i : lis){
      if(e.start == i.start && e.end==i.end || e.start == i.end && e.end==i.start ){
        return true;
      }
    }
    return false;
  }
  
  int getEnd(int start, ArrayList<Edge> lis){
    for(Edge i : lis){
      if(i.start == start){
        return i.end;
      }
    }
    return -1;
  }
  
  int getStart(int end, ArrayList<Edge> lis){
    for(Edge i : lis){
      if(i.end == end){
        return i.start;
      }
    }
    return -1;
  }
  
  
}

class Edge{
  int start;
  int end;
  int count;
  Edge(int start, int end){
    this(start,end,0);
  }
  Edge(int start, int end, int count)
  {
    this.start = start;
    this.end = end;
    this.count = count;
  }
  String toString(){
    return "Start: " + start + " End: " + end + " Cost: " + count;
  }
}

class EdgeCompare implements Comparator<Edge>{
  int compare(Edge a,Edge b){
    return ((Integer)a.count).compareTo((Integer)b.count);
  }
}

class EdgeCompare2 implements Comparator<Edge>{
  int compare(Edge a,Edge b){
    return ((Integer)a.start).compareTo((Integer)b.start);
  }
}


